package com.zhugang.week12;

import java.util.HashMap;
import java.util.Map;

/**
 * @program algorithms
 * @description: minWindow
 * @author: chanzhugang
 * @create: 2022/09/08 00:46
 */
public class MinWindow {

    /**
     * 76 最小覆盖子串
     *
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        // s中找覆盖t所有字符的最小子串
        // 难，想不到，编码也不好实现

        /**
         * 滑动窗口[l,r]
         * 1、如果没有覆盖，r++
         * 2、如果有覆盖，对比是否最小，l++，循环上面两个步骤，直到r>=n
         */

        int minWSize = Integer.MAX_VALUE;
        int minWStart = -1;
        int minWEnd = -1;
        // 模式串
        Map<Character, Integer> tmap = new HashMap<>();
        // 滑动窗口
        Map<Character, Integer> wmap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            int count = 1;
            if (tmap.containsKey(t.charAt(i))) {
                count += tmap.get(t.charAt(i));
            }
            // 统计模式串字符出现的频次（用于是否和滑动窗口匹配）
            tmap.put(t.charAt(i), count);
        }

        int n = s.length();
        int l = 0;
        int r = -1;
        while (l < n && r < n) {
            while (!match(wmap, tmap)) {
                // 不覆盖，r向右滑动
                r++;
                if (r > n - 1) {
                    break;
                }
                char c = s.charAt(r);
                if (tmap.containsKey(c)) {
                    int count = 1;
                    if (wmap.containsKey(c)) {
                        count += wmap.get(c);
                    }
                    wmap.put(c, count);
                }
            }

            if (match(wmap, tmap)) {
                // 覆盖了
                if (minWSize > r - l + 1) {
                    // 记录最小子串
                    minWSize = r - l + 1;
                    minWStart = l;
                    minWEnd = r;
                }
                char c = s.charAt(l);
                if (tmap.containsKey(c)) {
                    // l向右滑动，移除字符
                    int count = wmap.get(c);
                    if (count - 1 == 0) {
                        wmap.remove(c);
                    } else {
                        wmap.put(c, count - 1);
                    }
                }
                l++;
            }
        }
        if (minWStart == -1) {
            return "";
        }
        return s.substring(minWStart, minWEnd + 1);
    }

    private boolean match(Map<Character, Integer> wmap, Map<Character, Integer> tmap) {
        for (Map.Entry<Character, Integer> entry : tmap.entrySet()) {
            Character key = entry.getKey();
            if (!wmap.containsKey(key)) {
                return false;
            }
            if (wmap.get(key) < entry.getValue()) {
                return false;
            }
        }

        return true;
    }
}